package il.technion.math.zipfdistribution;

import java.security.Provider;
import java.security.SecureRandom;
import java.security.Security;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
import java.util.TreeSet;

public class DiscreteDistribution <T>
{
	Map<T,Integer> FreqMap; 
	Map<Integer,T> reverseMap;
	private final Random rnd;
	private TreeSet<IndexedDouble> discreeteData;
	private final int Size; 
	private double sum =0;
	public DiscreteDistribution(Map<T,Integer> frequencies , long seed)
	{	
		FreqMap = frequencies;
		Size = frequencies.size();
		
		rnd = new Random(seed);
		
		
//		rnd.setSeed(seed);
	
		reverseMap = new HashMap<Integer,T>();
		discreeteData = new TreeSet<IndexedDouble>();
		
		GenerateData();
	}
	
	public double getRate(int i)
	{
		return 0.0;
	}

	private void GenerateData()
	{
		//calculate total sum;
		
		Double[] partialSums = new Double[Size+1];
		Double[] partialValues = new Double[Size+1];
		double y;
		double t;
		double c = 0.0;
		
		
//		KahanSum(input)
//	    double sum = 0.0
//	    double c = 0.0          //A running compensation for lost low-order bits.
//	    for i = 1 to input.length do
//	        y = input[i] - c    //So far, so good: c is zero.
//	        t = sum + y         //Alas, sum is big, y small, so low-order digits of y are lost.
//	        c = (t - sum) - y   //(t - sum) recovers the high-order part of y; subtracting y recovers -(low part of y)
//	        sum = t             //Algebraically, c should always be zero. Beware eagerly optimising compilers!
//	        Next time around, the lost low part will be added to y in a fresh attempt.
//	    return sum
		
		
		int n =1;
		for (Map.Entry<T, Integer> entry : FreqMap.entrySet())
		{
			reverseMap.put(n, entry.getKey());
			partialValues[n] = (double)entry.getValue();
			
			y= partialValues[n]-c;
			t = sum+y;
			c = (t-sum)-y;
			sum = t;
			partialSums[n]=sum;
			n++;
		}
	
		
		//Populate the tree set:
		discreeteData.add(new IndexedDouble(0.0, 1));
		for(n =2; n<Size; n++)
		{
			discreeteData.add(new IndexedDouble((partialSums[n-1]),n));
		}
		
		
		
	}
	
	public Integer Sample()
	{
		Double sample = rnd.nextDouble();
		IndexedDouble chosen = discreeteData.lower(new IndexedDouble(sample*sum, -1));
		return chosen.index;
		
	}
	public double getSum()
	{
		return this.sum;
	}
	public double setSum(double sum)
	{
		return this.sum=sum;
	}
	
	

	public double getSize() {
		return Size;
	}

}
